{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Daily Temperatures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: dailyTemperatures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每日温度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组&nbsp;<code>temperatures</code>&nbsp;，表示每天的温度，返回一个数组&nbsp;<code>answer</code>&nbsp;，其中&nbsp;<code>answer[i]</code>&nbsp;是指对于第 <code>i</code> 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用&nbsp;<code>0</code> 来代替。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>temperatures</code> = [73,74,75,71,69,72,76,73]\n",
    "<strong>输出:</strong>&nbsp;[1,1,4,2,1,1,0,0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> temperatures = [30,40,50,60]\n",
    "<strong>输出:</strong>&nbsp;[1,1,1,0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> temperatures = [30,60,90]\n",
    "<strong>输出: </strong>[1,1,0]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;=&nbsp;temperatures.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>30 &lt;=&nbsp;temperatures[i]&nbsp;&lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [daily-temperatures](https://leetcode.cn/problems/daily-temperatures/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [daily-temperatures](https://leetcode.cn/problems/daily-temperatures/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[73,74,75,71,69,72,76,73]', '[30,40,50,60]', '[30,60,90]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        res = [0] * len(temperatures)\n",
    "        for i, t in enumerate(temperatures):\n",
    "            while stack and temperatures[stack[-1]] < t:\n",
    "                idx = stack.pop()\n",
    "                res[idx] = i-idx\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T):\n",
    "        \"\"\"\n",
    "        :type T: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not T:   return T\n",
    "        net = [float('inf')]*102\n",
    "        res = [0]*len(T)\n",
    "        for i in range(len(T)-1, -1, -1):\n",
    "            idx = min(net[t] for t in range(T[i]+1, 102))\n",
    "            if idx < float('inf'):\n",
    "                res[i] = idx-i\n",
    "            net[T[i]] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T):\n",
    "        \"\"\"\n",
    "        :type T: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not T:\n",
    "            return []\n",
    "        \n",
    "        stack = list()\n",
    "        T.reverse()\n",
    "        res = []\n",
    "        for i, val in enumerate(T):\n",
    "            while stack and T[stack[-1]] <= val:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                res.append(i - stack[-1])\n",
    "            else:\n",
    "                res.append(0)\n",
    "            stack.append(i)\n",
    "            \n",
    "            \n",
    "        res.reverse()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T):\n",
    "        \"\"\"\n",
    "        :type T: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ans = [0] * len(T)\n",
    "        stack = []\n",
    "        for i in range(len(T)-1,-1,-1):\n",
    "            while stack and T[i] >= T[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                ans[i] = stack[-1] - i\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T: 'List[int]') -> 'List[int]':\n",
    "        result = [0] * len(T)\n",
    "        stack = []\n",
    "        for i, t in enumerate(T):\n",
    "            while stack and t > T[stack[-1]]:\n",
    "                result[stack[-1]] = i - stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T):\n",
    "        \"\"\"\n",
    "        :type T: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        res = [0]*len(T)\n",
    "        for i in range(len(T)):\n",
    "            while stack and T[i]>T[stack[-1]]:\n",
    "                j = stack[-1]\n",
    "                res[j] = i-stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T):\n",
    "        \"\"\"\n",
    "        :type T: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = [0 for i in T]\n",
    "        stack=[[] for i in range(71)]\n",
    "        for index,temp in enumerate(T):\n",
    "            for li in stack[:temp-30]:\n",
    "                while li:\n",
    "                    i = li.pop()\n",
    "                    res[i]=index-i\n",
    "            stack[temp-30].append(index)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T: List[int]) -> List[int]:\n",
    "        if not T:\n",
    "            return []\n",
    "        tl = len(T)\n",
    "        stack = []\n",
    "        res = []\n",
    "        for i in range(tl-1,-1,-1):\n",
    "            days = 0\n",
    "            while stack and T[stack[-1]]<=T[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                days = stack[-1] - i\n",
    "            stack.append(i)\n",
    "            res.append(days)\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T: List[int]) -> List[int]:\n",
    "        '''\n",
    "        stack：维护一个顺序不变，从小到大排列的栈，比如对于75，栈为[71, 72, 76]\n",
    "        stack[-1] 栈顶元素\n",
    "        '''\n",
    "        result = [0] * len(T)\n",
    "        stack = []\n",
    "        for index in range(len(T)-1, -1, -1):\n",
    "            t = T[index]\n",
    "            while stack and t >= T[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                result[index] = stack[-1] - index\n",
    "            stack.append(index)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def dailyTemperatures(self,T):\n",
    "        nxt = [float('inf')] * 102  \n",
    "        #为什么是102？因为最高有100摄氏度，考虑极限情况：第i天的问题是100摄氏度，那么T[i]+1=101\n",
    "        #那102呢？\n",
    "        \n",
    "        ans = [0] * len(T)\n",
    "        for i in range(len(T) - 1, -1, -1):\n",
    "            #Use 102 so min(nxt[t]) has a default value\n",
    "            warmer_index = min(nxt[t] for t in range(T[i]+1, 102))\n",
    "            if warmer_index < float('inf'):\n",
    "                ans[i] = warmer_index - i\n",
    "            nxt[T[i]] = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T: List[int]) -> List[int]:\n",
    "        # 2020-02-23，二刷\n",
    "        # 暴力求解法，O(N2);\n",
    "        # 优化解法O(N),参考一刷代码----辅助栈\n",
    "        stack = []   # 辅助栈，记录的是idx，索引代表的温度严格递增\n",
    "        n = len(T)\n",
    "        rsl = [0 for _ in range(n)]\n",
    "\n",
    "        for key, value in enumerate(T):\n",
    "            if stack:\n",
    "                while stack and T[stack[-1]] < value:  # while循环,如75，71，69遇到value72，会把71，69值处理好\n",
    "                    rsl[stack[-1]] = key - stack[-1]\n",
    "                    stack.pop()\n",
    "            stack.append(key)\n",
    "\n",
    "        return rsl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T: List[int]) -> List[int]:\n",
    "        res = [0] * len(T)\n",
    "        stack = []\n",
    "        \n",
    "        for i in range(len(T)):\n",
    "            while (len(stack)!=0 and T[i] > T[stack[-1]]):\n",
    "                t = stack.pop()\n",
    "                res[t] = i - t\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from array import array\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        results = array('I')\n",
    "\n",
    "        for i in range(len(T)):\n",
    "            results.append(0)\n",
    "            while stack and T[stack[-1]] < T[i]:\n",
    "                results[stack[-1]] = i - stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "            \n",
    "        return results\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, T: List[int]) -> List[int]:\n",
    "        if not T:\n",
    "            return []\n",
    "        st, res = [], []\n",
    "        n = len(T)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and T[st[-1]] <= T[i]:\n",
    "                st.pop()\n",
    "            if not st:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                res.append(st[-1] - i)\n",
    "            st.append(i)\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stk = []\n",
    "        res = [0] * len(temperatures)\n",
    "        for i, t in enumerate(temperatures):\n",
    "            while stk and t > temperatures[stk[-1]]:\n",
    "                res[stk[-1]] = i-stk[-1]\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        \n",
    "        ans = [0] * len(temperatures)\n",
    "        temp = []\n",
    "\n",
    "        for i in range(len(temperatures)):\n",
    "            while temp and temperatures[i] >  temperatures[temp[-1]]:\n",
    "                pre_index = temp.pop()\n",
    "                ans[pre_index] = i - pre_index\n",
    "            temp.append(i)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        \n",
    "        if not temperatures: return []\n",
    "        \n",
    "        stack = []\n",
    "        n = len(temperatures)\n",
    "        ans = [0]*n\n",
    "        \n",
    "        for i in range(n):\n",
    "            while stack and temperatures[i]>temperatures[stack[-1]]:\n",
    "                ans[stack[-1]] = i-stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        cc=max(temperatures)\n",
    "        weight=[0]\n",
    "        dstack=[temperatures[-1]]#单减栈\n",
    "        temperatures[-1]=0\n",
    "        for i in range(len(temperatures)-2,-1,-1):\n",
    "            c=1\n",
    "            if dstack and temperatures[i]<dstack[-1] or not dstack:\n",
    "                dstack.append(temperatures[i])\n",
    "                weight.append(c)\n",
    "                temperatures[i]=c\n",
    "               # print(dstack,weight)\n",
    "            else:\n",
    "                while dstack and temperatures[i]>=dstack[-1]:\n",
    "                    c+=weight.pop()\n",
    "                    dstack.pop()\n",
    "                dstack.append(temperatures[i])\n",
    "                weight.append(c)\n",
    "                temperatures[i]=c\n",
    "                if len(dstack)==1:\n",
    "                    temperatures[i]=0\n",
    "                    weight[-1]=0\n",
    "               # print(dstack,weight)\n",
    "        return temperatures\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "    #     stack = []\n",
    "    #     n = len(temperatures)\n",
    "    #     res = [0] * n\n",
    "    #     for i in range(n):\n",
    "    #         while stack and temperatures[i] > temperatures[stack[-1]]:\n",
    "    #             j = stack.pop()\n",
    "    #             res[j] = i - j\n",
    "    #         stack.append(i)\n",
    "    #     return res\n",
    "\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(temperatures)\n",
    "        # res = [0] * n\n",
    "        for i in range(n):\n",
    "            while stack and temperatures[i] > temperatures[stack[-1]]:\n",
    "                j = stack.pop()\n",
    "                temperatures[j] = i - j\n",
    "            stack.append(i)\n",
    "        for idx in stack:\n",
    "            temperatures[idx] = 0\n",
    "\n",
    "        return temperatures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        ret = [0] *len(temperatures)\n",
    "        for i in range(len(temperatures)-1,-1,-1):\n",
    "            while stack and temperatures[stack[-1]]<=temperatures[i]:\n",
    "                p = stack.pop()\n",
    "            if stack:\n",
    "                ret[i]=stack[-1]-i\n",
    "            stack.append(i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        tempreture_record = []\n",
    "        n = len(temperatures)\n",
    "        res = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            while tempreture_record != [] and temperatures[tempreture_record[-1]] < temperatures[i]:\n",
    "                res[tempreture_record[-1]] = i - tempreture_record[-1]\n",
    "                tempreture_record.pop()\n",
    "            tempreture_record.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        que = [] \n",
    "        for i in range(len(temperatures)):\n",
    "            if not que:\n",
    "                que.append(i)\n",
    "                continue\n",
    "            while que and temperatures[i]>temperatures[que[-1]] :\n",
    "                index = que.pop()\n",
    "                temperatures[index] = i-index \n",
    "            que.append(i)\n",
    "            \n",
    "        for i in que:\n",
    "            temperatures[i] = 0\n",
    "                \n",
    "        return (temperatures )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        tq = deque()\n",
    "        re = [0] * len(temperatures)\n",
    "        for i in range(len(temperatures)):\n",
    "            if not tq:\n",
    "                tq.append(i)\n",
    "            else:\n",
    "                while tq and temperatures[i]>temperatures[tq[-1]]:\n",
    "                    cur_index = tq.pop()\n",
    "                    re[cur_index] = i-cur_index\n",
    "                tq.append(i)\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        temp_stack = [0]\n",
    "        res = [0] * len(temperatures)\n",
    "        for index in range(1, len(temperatures)):\n",
    "            while len(temp_stack) > 0 and temperatures[index] > temperatures[temp_stack[-1]]:\n",
    "                res[temp_stack[-1]] = index - temp_stack[-1]\n",
    "                temp_stack.pop()\n",
    "            temp_stack.append(index)\n",
    "            index += 1\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        rst = [0] * len(temperatures)\n",
    "        for i in range(len(temperatures)):\n",
    "            while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:\n",
    "                rst[stack[-1]] = i - stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for i, t in enumerate(temperatures):\n",
    "            while stack and temperatures[stack[-1]] < t:\n",
    "                idx = stack.pop(-1)\n",
    "                temperatures[idx] = i - idx\n",
    "            stack.append(i)\n",
    "        for i in stack:\n",
    "            temperatures[i] = 0\n",
    "        return temperatures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        ans = [0]*len(temperatures)\n",
    "        ans[-1] = 0\n",
    "        for i in range(len(temperatures) - 2, -1, -1):\n",
    "            if temperatures[i] < temperatures[i + 1]:\n",
    "                ans[i] = 1\n",
    "            elif temperatures[i] == temperatures[i + 1]:\n",
    "                ans[i] = ans[i + 1] + 1 if ans[i + 1] != 0 else 0\n",
    "            else:\n",
    "                pre = i + 1\n",
    "                cur = pre + ans[pre]\n",
    "                while cur != pre and temperatures[i] >= temperatures[cur]:\n",
    "                    pre = cur\n",
    "                    cur = pre + ans[pre]\n",
    "                if cur == pre:\n",
    "                    ans[i] = 0\n",
    "                else:\n",
    "                    ans[i] = cur - i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        ans = [0] * len(temperatures)\n",
    "        cup = []\n",
    "        for i in range(len(temperatures)):\n",
    "            if not cup:\n",
    "                cup.append(i)               \n",
    "            else:\n",
    "                #print(cup,i)              \n",
    "                while cup and temperatures[i] > temperatures[cup[-1]]:                    \n",
    "                    ans[cup[-1]] = i - cup[-1]\n",
    "                    #print(ans)\n",
    "                    cup.pop()\n",
    "                cup.append(i)\n",
    "        #print(ans)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        res = [0] * len(temperatures)\n",
    "        stack = [0] # 栈里存放下标,从栈顶[下标0]到栈尾，应是单调递增\n",
    "        for i in range(1,len(temperatures),1):\n",
    "            if temperatures[i] <= temperatures[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while len(stack) > 0 and temperatures[i] > temperatures[stack[-1]]:\n",
    "                    res[stack[-1]] = i - stack[-1]\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        nxt = dict()\n",
    "        n = len(temperatures)\n",
    "        answer = [0] * n\n",
    "        big = 10000000\n",
    "        n = len(temperatures)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            min_next_idx = min([nxt.get(j, big) for j in range(temperatures[i] + 1, 102)])\n",
    "            if min_next_idx != big:\n",
    "                answer[i] = min_next_idx - i\n",
    "            nxt[temperatures[i]] = i \n",
    "        return answer\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(temperatures)\n",
    "        # answer = [0]*n\n",
    "        # next1 = {}\n",
    "        # big = 100000000\n",
    "        # for i in range(n-1, -1, -1):\n",
    "        #     x = temperatures[i]\n",
    "        #     min_next_idx = min([next1.get(j, big) for j in range(temperatures[i]+1, 102)])\n",
    "        #     if min_next_idx != big:\n",
    "        #         answer[i] = min_next_idx - i \n",
    "        #     next1[temperatures[i]] = i \n",
    "        # return answer\n",
    "        # n = len(temperatures)\n",
    "        # answer = [0]*n\n",
    "        # stack = []\n",
    "        # for i in range(n):\n",
    "        #     x = temperatures[i]\n",
    "        #     while stack and x > temperatures[stack[-1]]:\n",
    "        #         prev_idx = stack.pop()\n",
    "        #         answer[prev_idx] = i - prev_idx\n",
    "        #     stack.append(i)\n",
    "        # return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        HISTORY = [0] * 71  # 记录这个温度最近出现的时间, index 是温度值，value 是最近出现的时间\n",
    "        for idx in range(len(temperatures)-1, -1, -1):\n",
    "            # print(temperatures)\n",
    "            # print(HISTORY)\n",
    "            temp = temperatures[idx] - 30   # 温度减30\n",
    "            HISTORY[temp] = idx\n",
    "            # recent = min(HISTORY[temp+1:])  # 最近一次高于今天的温度\n",
    "            moreL = [i for i in HISTORY[temp+1:] if i != 0]\n",
    "            if not moreL: moreL += [0]\n",
    "            after = min(moreL)\n",
    "            # print(after,idx)\n",
    "            temperatures[idx] = after - idx if after != 0 else 0\n",
    "        return temperatures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans, nxt, big = [0]*n, dict(), 10**9\n",
    "        for i in range(n-1, -1, -1):\n",
    "            warmer_index = min(nxt.get(t, big) for t in range(temperatures[i]+1, 102))\n",
    "            if warmer_index != big:\n",
    "                ans[i] = warmer_index - i\n",
    "            nxt[temperatures[i]] = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "\n",
    "        nxt=dict()\n",
    "        big=10**9\n",
    "        n=len(temperatures)\n",
    "        res=[0]*n\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            warmer_index=min(nxt.get(t,big) for t in range(temperatures[i]+1,102))\n",
    "            if warmer_index !=big:\n",
    "                res[i]=warmer_index-i \n",
    "            nxt[temperatures[i]]=i \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        result = [0] * len(temperatures)\n",
    "        for i in range(len(temperatures)-1, -1, -1):\n",
    "            highest = True\n",
    "            while stack:\n",
    "                value, index = stack[-1]\n",
    "                if value > temperatures[i]:\n",
    "                    result[i] = index-i\n",
    "                    highest = False\n",
    "                    break\n",
    "                else:\n",
    "                    stack.pop()\n",
    "            stack.append((temperatures[i], i))\n",
    "            if highest:\n",
    "                result[i] = 0\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        if not temperatures:\n",
    "            return []\n",
    "        stack = []\n",
    "        res = [0]*len(temperatures)\n",
    "        for i in range(len(temperatures)):\n",
    "            while stack and temperatures[i]>temperatures[stack[-1]]:\n",
    "                cur = stack.pop()\n",
    "                res[cur] = i-cur\n",
    "            stack.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        length = len(temperatures)\n",
    "        ans = [0] * length\n",
    "        stack = []\n",
    "        for i in range(length):\n",
    "            temperature = temperatures[i]\n",
    "            while stack and temperature > temperatures[stack[-1]]:\n",
    "                prev_index = stack.pop()\n",
    "                ans[prev_index] = i - prev_index\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack, n = [0], len(temperatures)\n",
    "        ans = [0 for _ in range(n)]\n",
    "        if n < 2: return stack\n",
    "        for i in range(1, n):\n",
    "            while stack and temperatures[stack[-1]] < temperatures[i]:\n",
    "                ans[stack[-1]] = i - stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        answer = [0] * n\n",
    "        m = max(temperatures)\n",
    "\n",
    "        for i in range(n):\n",
    "            if temperatures[i] != m:  # 最高温度 answer[i]==0 跳过计算\n",
    "                for j in range(i+1, n):\n",
    "                    answer[i] += 1\n",
    "                    if i != 0:  # 边界条件 1\n",
    "                        if temperatures[i] == temperatures[i-1]:  # 相邻的相同温度，天数差为 1\n",
    "                            answer[i] = answer[i-1] - 1 \n",
    "                            break\n",
    "                    if temperatures[i] < temperatures[j]:\n",
    "                        break\n",
    "                    if j == n-1:  # 边界条件 2\n",
    "                        answer[i] = 0\n",
    "\n",
    "        answer = [0 if x < 0 else x for x in answer]  # 负值 -> 0\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        result = [0 for _ in range(len(temperatures))]\n",
    "        copy_temperatures = copy.copy(temperatures)\n",
    "        for _ in range(len(temperatures)):\n",
    "            if not stack:\n",
    "                stack.append(_)\n",
    "            else:\n",
    "                top = stack[len(stack)-1]\n",
    "                top_value = copy_temperatures[top]\n",
    "                tmp = temperatures[_]\n",
    "                if top_value >= tmp:\n",
    "                    # 如果小于等于栈顶元素，加入到栈里\n",
    "                    stack.append(_)\n",
    "                else:\n",
    "                    while top_value < tmp:\n",
    "                        result[top] = _ - top\n",
    "                        stack.pop(len(stack) - 1)\n",
    "                        if stack:\n",
    "                            top = stack[len(stack)-1]\n",
    "                            top_value = copy_temperatures[top]\n",
    "                        else:\n",
    "                            break\n",
    "                    stack.append(_)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        # 单调栈\n",
    "        n = len(temperatures)\n",
    "        ans = [0 for i in range(n)]\n",
    "        stack = [0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(len(stack)):\n",
    "                index = stack.pop()\n",
    "                if temperatures[i] > temperatures[index]:\n",
    "                    ans[index] = i - index\n",
    "                   \n",
    "                else:\n",
    "                    stack.append(index)\n",
    "                    stack.append(i)\n",
    "                    break\n",
    "            stack.append(i)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temp: List[int]) -> List[int]:\n",
    "        n = len(temp)\n",
    "        # ans\n",
    "        ans = [0] * n\n",
    "        \"\"\"\n",
    "        模拟栈\n",
    "        h = 0, t = -1\n",
    "        h > t, 则 empty()\n",
    "        stack[++ t], 则 offer()\n",
    "        stack[t --], 则 poll()\n",
    "        \"\"\"\n",
    "        stack = [0] * n\n",
    "        h, t = 0, -1\n",
    "        for i in range(n):\n",
    "            # 空栈直接插入\n",
    "            if h > t:\n",
    "                t += 1\n",
    "                stack[t] = i\n",
    "            else:\n",
    "                # 当前数 > 栈顶, 开始出栈\n",
    "                while h <= t and temp[i] > temp[stack[t]]:\n",
    "                    # 当前下标 i 减去 栈顶代表的下标\n",
    "                    ans[stack[t]] = i - stack[t]\n",
    "                    t -= 1\n",
    "                # 把当前数插入到栈中\n",
    "                t += 1\n",
    "                stack[t] = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(temperatures)\n",
    "        res = []\n",
    "        # 后一个更大元素 --》 后往前遍历 + 单调递减栈\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack!=[] and temperatures[i] >= temperatures[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack == []:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                res.append(stack[-1] - i)\n",
    "            stack.append(i)\n",
    "            # print(stack)\n",
    "        print(res[::-1])\n",
    "        return res[::-1]\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        stack = [-1 for i in range(n)]\n",
    "        ans = [0 for i in range(n)]\n",
    "        top = -1\n",
    "        for i, t in enumerate(temperatures):\n",
    "            if top == -1 or temperatures[stack[top]] > t:\n",
    "                # push stack\n",
    "                top += 1\n",
    "                stack[top] = i\n",
    "            else:\n",
    "                # clear stack\n",
    "                while top!=-1 and temperatures[stack[top]] < t:\n",
    "                    ans[stack[top]] = i - stack[top]\n",
    "                    top-=1\n",
    "                # push stack\n",
    "                top += 1\n",
    "                stack[top] = i\n",
    "        \n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "\n",
    "        list_stack = []\n",
    "        out = list(range(len(temperatures)))\n",
    "        ind=0\n",
    "        while (len(temperatures)-ind)+len(list_stack):\n",
    "            if len(list_stack)==0 or (ind < len(temperatures) and temperatures[list_stack[-1]]>=temperatures[ind]):\n",
    "                list_stack.append(ind)\n",
    "                ind=ind+1\n",
    "            else:\n",
    "                o = list_stack.pop(-1)\n",
    "                if ind == len(temperatures):\n",
    "                    out[o] = 0\n",
    "                else:\n",
    "                    out[o] =ind -o \n",
    "            \n",
    "        return out\n",
    "                 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        sl = SortedList()\n",
    "        n = len(temperatures)\n",
    "        ans = [0] * n\n",
    "        g = defaultdict(list)\n",
    "        for i,x in enumerate(temperatures):\n",
    "            g[x].append(i)\n",
    "        for x in sorted(set(temperatures))[::-1]:\n",
    "            for i in g[x]:\n",
    "                p = sl.bisect_right(i)\n",
    "                if p < len(sl): ans[i] = sl[p] - i\n",
    "            for i in g[x]: sl.add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        sl = SortedList()\n",
    "        n = len(temperatures)\n",
    "        ans = [0] * n\n",
    "        g = defaultdict(list)\n",
    "        for i,x in enumerate(temperatures): g[x].append(i)\n",
    "        for x in sorted(set(temperatures))[::-1]:\n",
    "            for i in g[x]:\n",
    "                p = sl.bisect_right(i)\n",
    "                if p < len(sl): ans[i] = sl[p] - i\n",
    "            for i in g[x]: sl.add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        res=[0]*len(temperatures)\n",
    "        pointer=[0]\n",
    "        for i,t in enumerate(temperatures[1:]):\n",
    "            i+=1\n",
    "            if t<=temperatures[pointer[-1]]:\n",
    "                pointer.append(i)\n",
    "            else:\n",
    "                for ele_p in pointer[::-1]:\n",
    "                    if temperatures[ele_p]<t:\n",
    "                        res[pointer[-1]]=i-pointer[-1]\n",
    "                        pointer.pop(-1)\n",
    "                pointer.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack=deque()\n",
    "        ans=[0]*len(temperatures)\n",
    "        for i,t in enumerate(temperatures):\n",
    "            if not stack:\n",
    "                stack.append((t,i))\n",
    "            else:\n",
    "                while stack and stack[-1][0]<t:\n",
    "                    _,prei=stack.pop()\n",
    "                    ans[prei]=i-prei\n",
    "                stack.append((t,i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "\n",
    "        ans = [0] * len (temperatures)\n",
    "        que = []\n",
    "\n",
    "        for cur_idx, cur_temp in enumerate(temperatures):\n",
    "            \n",
    "            while(que):\n",
    "                temp, idx = heapq.heappop(que)\n",
    "                if temp < cur_temp:\n",
    "                    ans[idx] = cur_idx - idx\n",
    "                elif cur_idx != len(temperatures) - 1:\n",
    "                    heapq.heappush(que, (temp, idx))\n",
    "                    break\n",
    "\n",
    "            heapq.heappush(que, (cur_temp, cur_idx))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        answer = [0] * len(temperatures)\n",
    "        for i, n in enumerate(temperatures):\n",
    "            while True:\n",
    "                if len(stack) == 0:\n",
    "                    stack.append((i, n))\n",
    "                    break\n",
    "                idx, top = stack[-1]\n",
    "                if top < n:\n",
    "                    answer[idx] = i - idx\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append((i, n))\n",
    "                    break\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        result = [0 for i in range(len(temperatures))]\n",
    "        for (index,i) in enumerate(temperatures):\n",
    "            if len(stack) == 0:\n",
    "                stack.append((index,i))\n",
    "            else:\n",
    "                while len(stack) > 0 and stack[-1][1] < i:\n",
    "                    last_index,last_i = stack.pop(-1)\n",
    "                    result[last_index] = index - last_index\n",
    "                stack.append((index,i))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        import heapq\n",
    "        ans: list[int] = [0] * len(temperatures)\n",
    "        heap: list[tuple[int, int]] = []\n",
    "        for index, temperature in enumerate(temperatures):\n",
    "            while heap:\n",
    "                min_, i = heapq.heappop(heap)\n",
    "                if min_ < temperature:\n",
    "                    ans[i] = index - i\n",
    "                else:\n",
    "                    heapq.heappush(heap, (min_, i))\n",
    "                    break\n",
    "            heapq.heappush(heap, (temperature, index))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        lstStack = []\n",
    "        iLen = len(temperatures)\n",
    "        lstRes = [0]*iLen\n",
    "        for i in range(iLen-1):\n",
    "            if temperatures[i+1] > temperatures[i]:\n",
    "                lstRes[i]=1\n",
    "                while lstStack and temperatures[i+1] > lstStack[-1][0]:\n",
    "                    iVal, iIndex = lstStack.pop()\n",
    "                    lstRes[iIndex] = i+1-iIndex\n",
    "            else:\n",
    "                lstRes[i]=0\n",
    "                lstStack.append([temperatures[i], i])\n",
    "        return lstRes\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
